package 滑动窗口And双指针.双指针;
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
/**
 * 从这道题 中 也看看出 来 回溯  算法 解决问题的 局限性
 * 这是不是 我 用 回溯 方法的 写不出来  （个人问题）
 * 
 * 
 * 如果 这道题 没有 要求 是连续的 话 这样 的 写法 是可以 解决的
 * 
 * 下面 对 该题 进行 改 编  
 * 就是 不要求 连续  的 子数组 
 * 只要是 其 子数组 就行
 * 
 * @author I adore you
 *
 */
public class leetcode713乘积小于k的子数组 {
	public static void main(String []args) {
		int nums[] = {10,5,2,6};
		int k = 100;
//		int nums [] =  {1,2,3};
//		int k = 0;
		process(nums,k,1,0,nums.length);
//		System.out.println(ans);
		System.out.println(ans.size());
		process(nums,0,k,1);
		System.out.println(res);
		System.out.println(process(nums,k));
		
	}
	/**
	 * 递归 回溯 好像     
	 * 是不是   有了 一个 新的 收获  
	 * 对于 这种         叶子  节点   和 非叶子 节点 都是 要收集的 答案的 时候  是不是 basecase  
	 * 就可以省掉了   直接 在  for  进行 一个 过滤   而且 这样过滤的 话 效率 会更高一些  
	 */
	static List<List<Integer>>  ans = new ArrayList<>();
	static Deque<Integer> path = new ArrayDeque<>();
	static void process(int nums[],int k,int multiply,int index,int len){
		for(int i = index ; i < len ;i++) {
			if(nums[i] * multiply < k) {
				path.addLast(nums[i]);
				ans.add(new ArrayList<>(path));
				process(nums,k,multiply * nums[i],i + 1,len);
//				path.poll();
				path.removeLast();
			}		
		}
	}
	static int res = 0;
	static void  process(int nums[],int index,int k,int temp) {
//		if( temp >= k)
//			return 0;
//		if(index == nums.length || temp < k)
//			return 1;
//		int ans = 0;
		for(int i = index ;i < nums.length ; i++) {
			if(temp * nums[i] < k) {
				res++;
				process(nums,i + 1,k,temp * nums[i]);
			}
		}
	
	}
	/**
	 *  将暴力 递归  直接 改成   循环
	 *  纯纯  O(n ^ 2)
	 *  滑动窗口And双指针.双指针 还有个 小小的优化
	 */
	static int answer = 0;
	static int process(int nums[] ,int k) {
		int len = nums.length;
		for(int i = 0; i < len ;i++) {
			int temp = 1;
//			while(true) {
//				if
//			}
/**
			for(int j = i ;j < len ;j ++) {
				if(temp * nums[j] < k) {
					answer++;
					temp *= nums[j];
				}
				else
				break;
			}
			下面  这个 for 循环  比上面 这个  循环  要简洁 一些 
 */
			for(int j = i ;j < len && temp * nums[j] < k;j ++) {
					answer++;
					temp *= nums[j];
			}
		}
		return answer;
	}
	
}